#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;

vector<int> productExceptSelf(vector<int>& nums) {
  int len = nums.size();
  vector<int> ret = vector<int>(len,1);

  int left = 1;
  ret[len-1] = left;
  for(int i=len-2; i>=0; --i) {
    left *= nums[i+1];
    ret[i] = left;
  }

  int right = 1;
  for(int i=1; i<len; ++i) {
    right *= nums[i-1];
    ret[i] *= right;
  }

        
  return ret;  
}



int main(int argc,char *argv[]) {

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);
  vector<int> in = {1,2,3,4};
  vector<int> ret = productExceptSelf(in);
  for(int i=0; i<ret.size(); ++i)
    cout<<ret.at(i)<<",";

  cout<<endl;
  //func();

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
       <<"leetcode server time consuming should be less than 500ms"<<endl
       << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;



  return 0;
}
